package tcm.com.gistone.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.TreeSet;

public class Combination {

    public static void main(String[] args) {

        String[] dataList ={"1","2","3","4","5"};
        arrangementSelect(dataList,2);

    }
    /**
     * 计算阶乘数，即n! = n * (n-1) * ... * 2 * 1
     * @param n
     * @return
     */
    private static long factorial(int n) {
        return (n > 1) ? n * factorial(n - 1) : 1;
    }

    /**
     * 计算排列数，即A(n, m) = n!/(n-m)!
     * @param n
     * @param m
     * @return
     */
    public static long arrangement(int n, int m) {
        return (n >= m) ? factorial(n) / factorial(n - m) : 0;
    }

    /**
     * 计算组合数，即C(n, m) = n!/((n-m)! * m!)
     * @param n
     * @param m
     * @return
     */
    public static long combination(int n, int m) {
        return (n >= m) ? factorial(n) / factorial(n - m) / factorial(m) : 0;
    }
    /**
     * 排列选择（从列表中选择n个排列）
     * @param dataList 待选列表
     * @param n 选择个数
     */
    public static void arrangementSelect(String[] dataList, int n) {
        System.out.println(String.format("A(%d, %d) = %d", dataList.length, n, arrangement(dataList.length, n)));
        arrangementSelect(dataList, new String[n], 0);
    }

    /**
     * 排列选择
     * @param dataList 待选列表
     * @param resultList 前面（resultIndex-1）个的排列结果
     * @param resultIndex 选择索引，从0开始
     */
    private static void arrangementSelect(String[] dataList, String[] resultList, int resultIndex) {
        int resultLen = resultList.length;
        if (resultIndex >= resultLen) { // 全部选择完时，输出排列结果
            System.out.println(Arrays.asList(resultList));
            return;
        }

        // 递归选择下一个
        for (int i = 0; i < dataList.length; i++) {
            // 判断待选项是否存在于排列结果中
            boolean exists = false;
            for (int j = 0; j < resultIndex; j++) {
                if (dataList[i].equals(resultList[j])) {
                    exists = true;
                    break;
                }
            }
            if (!exists) { // 排列结果不存在该项，才可选择
                resultList[resultIndex] = dataList[i];
                arrangementSelect(dataList, resultList, resultIndex + 1);
            }
        }
    }
    /**
     * 组合选择（从列表中选择n个组合）
     * @param dataList 待选列表
     * @param n 选择个数
     */
    public static void combinationSelect(String[] dataList, int n) {
        System.out.println(String.format("C(%d, %d) = %d", dataList.length, n, combination(dataList.length, n)));
        combinationSelect(dataList, 0, new String[n], 0);
    }

    /**
     * 组合选择
     * @param dataList 待选列表
     * @param dataIndex 待选开始索引
     * @param resultList 前面（resultIndex-1）个的组合结果
     * @param resultIndex 选择索引，从0开始
     */
    private static void combinationSelect(String[] dataList, int dataIndex, String[] resultList, int resultIndex) {
        int resultLen = resultList.length;
        int resultCount = resultIndex + 1;
        if (resultCount > resultLen) { // 全部选择完时，输出组合结果
            System.out.println(Arrays.asList(resultList));
            return;
        }

        // 递归选择下一个
        for (int i = dataIndex; i < dataList.length + resultCount - resultLen; i++) {
            resultList[resultIndex] = dataList[i];
            combinationSelect(dataList, i + 1, resultList, resultIndex + 1);
        }
    }
    /*private static int NUM = 2;
     
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入X个数，用逗号分割：");
        String str = input.nextLine();
        String[] datas = str.split(",");
        System.out.println("请输入数字Y:");
        NUM = input.nextInt();
        if (NUM > datas.length) {
            System.out.println("输入的Y必须小于等于X!");
            return;
        }
        combine(Arrays.asList(datas));
    }
    public static  ArrayList<TreeSet<String>>  combine(List<String> datas) {
        TreeSet<String> set = new TreeSet<String>();
        for(String str : datas) {
            set.add(str);
        }
         
        ArrayList<TreeSet<String>> subset = getSubset(set);
        for (TreeSet<String> strings : subset) {
            
        }
        for (String string : subset){

            System.out.println(string);
        }
        return  subset;
    }

    public static String[] getBinaryValue(TreeSet<String> set) {
        int size = set.size();
        int m = (int) Math.pow(2, size) - 1;
        String[] result = new String[m + 1];
        for (int i = m; i > -1; i--) {
            StringBuffer sb = new StringBuffer(Integer.toBinaryString(i));
            int length = sb.length();
            if (length < size) {
                for (int j = 0; j < size - length; j++) {
                    sb.insert(0, "0");
                }
            }
            result[i] = sb.toString();
        }
        return result;
    }

    public static ArrayList<TreeSet<String>> getSubset(TreeSet<String> set) {
        ArrayList<TreeSet<String>> result = new ArrayList<TreeSet<String>>();
        String[] items = new String[set.size()];
        int i = 0;
        for (String item : set) {
            items[i++] = item;
        }
        String[] binaryValue = getBinaryValue(set);
        for (int j = 0; j < binaryValue.length; j++) {
            String value = binaryValue[j];
            TreeSet<String> subset = new TreeSet<String>();
            for (int k = 0; k < value.length(); k++) {
                if (value.charAt(k) == '1')
                    subset.add(items[k]);
            }
            if(subset.size() == NUM)
                result.add(subset);
        }
 
        return result;
    }*/
}